home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / aminet / util / pack / xpkrdcn.lha / xpkRDCN / RDCN.doc < prev    next >
Text File  |  1992-12-12  |  8KB  |  172 lines
  1.  
  2.                                    RDCN
  3.  
  4.          An implementation of Ross Data Compression for the Amiga
  5.                                  Featuring
  6.                     Fast compression and decompression
  7.                       The fastest overall xpk-library
  8.  
  9.  
  10.             Some copyright 1992, Niklas Sjöberg, but totally PD
  11.  
  12.  
  13. LEGAL STUFF
  14. ~~~~~~~~~~~
  15. This library (xpkRDCN.library) may be freely disributed with any kind of
  16. software, as long as no profit is made of the other software. Also, ALL
  17. files, source, docs and binary, must be in the same package. If RDCN is put
  18. in the xpkdev-/xpkusr-archives, source and binary may be splitted.
  19.  
  20. The author takes NO RESPONSABILITY for any damage of lost data caused by
  21. this library. The actual algorithm is 100% OK but bugs may have sneaked
  22. into the code. RDCN have been tested on more than 100Mb of data and have been
  23. compared to the original files. No differences where found. However crunched
  24. data is always more dangerous to use than uncrunched data. It just takes one
  25. single bit that is faulty to make a large part, or even the whole file,
  26. useless.
  27.  
  28. The actual algorithm (in this version) is (c) Ed Ross, see bottom of file.
  29.  
  30.  
  31. WHY? and WHAT IS RDCN?
  32. ~~~~~~~~~~~~~~~~~~~~~~
  33. RDCN is based on a very simple, but yet effective AND fast algorithm published
  34. in `The C Users Journal` Oct '92. It was transferred to Amiga assembly code by
  35. me, since I lacked a both-way fast xpk-packer. The assembly code has been very
  36. much optimized and I think that higher CPS-rates won't be possible if the RDC
  37. method is used. For all you that are interested in compression-stuff:
  38.  
  39. RDCN works with 65K (approx) inbuffers. It also allocates a hash-table of
  40. 4096 entries (that's 16 Kb). Before each 'sequence' RDCN stores a control-
  41. word, in order to distinguish compressed bytes from uncompressed ones. A bit
  42. which is zero indicates that the next byte is uncompressed. Just to be
  43. compatible with the original RDC, RDCN uses bit 15 as byte1-indicator, bit
  44. 14 as byte2 indicator etc. etc. Now, how do the data get compressed? :)
  45.  
  46. o First RDCN checks if the next inbyte equals to the current. If so, get next
  47.   byte, see if that equals to the next etc. etc. RDCN also makes sure that we
  48.   don't advance >4113 bytes.
  49. o If at least 3 bytes were identical, we can use RLE (Run Length Encoding)
  50.   o Were there <19 characters repeated?
  51.     o Yes! This is a short RLE. Since there were at least 3 repeated bytes
  52.       we subtract 3 from the number of repeated bytes. Gee! Max number of
  53.       repeated bytes is now 15, 4 bits. The other four bits (in this case
  54.       zero) tells RDCN which compression method that was used. Next we store
  55.       first the crunched byte (4 bit code, 4 bit 'count') and next the byte
  56.       to be repeated.
  57.       Jump to top.
  58.   o No! We need to use more than one byte for compression code and 'count'.
  59.       Subtract 19 from count. Since we made sure that number of repeated chars
  60.       was less than 4114 we now only need 12 bits for count. Set the 4 bit
  61.       compression-code to 1, store that 4 bits + 4 bits of count. Store 8
  62.       bit count and the byte to repeat.
  63.       Jump to top.
  64. o We found no repeating characters. Use the sliding dictionary instead.
  65.   Calculate a hash between 0 and 4095. Look in dictionary at offset 'hash'.
  66.   (The hash is calculated by using the current byte and the two following)
  67.   Get possible pointer and store the new one (the current position) 
  68. o See if the old pointer in hash_table[hash] wasn't zero!
  69.   o No! Sorry, nothing do to. Just copy the current byte to outbuffer.
  70.     Jump to top.
  71.   o Yes! First make sure the three byte sequence isn't located > 4098 bytes
  72.     away. If it is, we can't compress! ('gap' only uses 12 bits)
  73.     Now, start comparing our current bytes in source to the 'old' bytes which
  74.     hash_table[hash] pointed to. If >271 bytes equal we stop since we can't
  75.     handle longer patterns than 271 bytes (max 8 bits in count).
  76.     o Next, if less than 3 bytes didn't match, we can't compress. Copy current
  77.       byte to outbuffer and jump to top.
  78.     o Did at least three bytes match, but no more than 15?
  79.       o Yes! A short pattern. Combine count (4 bits) with 4 bits from 'gap'
  80.         (gap is the offset from last pattern to current pattern). Next store
  81.         8 more bits from gap (we have subtracted three from gap since at
  82.         least three bits matched and gap can thus be as large as 4098 bytes).
  83.       o No! Encode this as a long pattern. This pattern is at least 16 bytes
  84.         long, so subtract 16 from count. Since we made sure the pattern was no
  85.         longer than 271 bytes we only need 8 bits for count. Gap still need
  86.         12 bits, so combine 4 of them with the four control bits (which are
  87.         set to 2!), store the next 8 gap-bits and last the 8 bit count.
  88. o We're done! Proceed with a jump to top to search for RLE on next source
  89.   byte.
  90.  
  91. To sum up :
  92.  ______________________________________________________________
  93. |Type          |       Byte 1       |    Byte 2   |   Byte 3  |
  94.  --------------------------------------------------------------
  95. |Short RLE     | 0 |  count         | character   | not used  |
  96.  --------------------------------------------------------------
  97. |Long  RLE     | 1 |  low count     | high count  | character |
  98.  --------------------------------------------------------------
  99. |Long  Pattern | 2 |  low offset    | high offset | count     |
  100.  --------------------------------------------------------------
  101. |Short Pattern | 3-15 |  low offset | high offset | not used  |
  102.  ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
  103.  
  104. Have a look at the source. If you find a smart way to speed it up PLEASE
  105. do it and release both binary and cource code into the public domain!!
  106. Improving compression a bit wouldn't be that hard. Even though RDCN compress
  107. fairly well, we really could use BLZW instead (even though it unpacks slow!).
  108. Compression rate isn't the most important thing here, we want speed! :)
  109.  
  110. USAGE:
  111. ~~~~~~
  112. Most of you probably skipped to this section directly :)
  113. RDCN packs fairly well, about 32 % on AmigaVision executable, about
  114. 45-50% on textfiles. On really simple textfiles, like a 'list dh0: ALL' RDCN
  115. may manage to pack upto a CF of 70-80%. On _really_ redundant data, like a
  116. a file full of zeroes RDCN should packs as good as any RLE-packer.
  117.  
  118. The main intention with this packer is 'to go where no packer ever has gone
  119. before' :) Since RDCN is optimized on both packing and depacking it is
  120. intended for devices/dirs you _normally_ wouldn't pack. A C-programming device
  121. would be a good example. It takes a lot of space, data is fairly simple and
  122. you want a decent access speed. However, until a real version of XFH is
  123. released (one which doesn't copy file, wait until it is closed and the packs
  124. it, but rather pack chunks) you may want to wait with the most speed demanding
  125. devices.
  126.  
  127. Since I don't have 'xBench' I've timed BLZW and NUKE a couple of times
  128. and compared them to RDCN (timed using the built-in function in Csh).
  129.  
  130. Method   Packing   Unpacking   Packing   Unpacking   Compression
  131.          Memory     Memory      Speed      Speed        Ratio
  132. ------   -------   ---------   -------   ---------   -----------
  133.  RDCN      16K        0K        150 K/s    600 K/s       33.0%   ; binary
  134.  RDCN      16K        0K        150 K/s    600 K/s       45.0%   ; text
  135.  
  136. When packing all the programs/files in the SAS/C 6.1 package RDCN reduced
  137. size by 42%.
  138.  
  139.  
  140. A more interesting benchmark:
  141.  
  142. FILE: Fish contents 1-650 (some disk missing :-() + AmigaVision executable
  143. FILESIZE: 1725 Kb (ie. around 1766400 bytes)
  144. LOCATION: RAM:
  145. MACHINE: A3000/25 w SCRAM
  146.  
  147. METHOD        PACKTIME    DEPACKTIME    RATIO
  148. NUKE        44.36 secs    4.92 secs    54 %
  149. BLZW.60        13.34 secs    6.70 secs    46 %
  150. RDCN        11.24 secs    4.34 secs    41 %
  151.  
  152. Since NUKE depacks 630 Kb/sec this would indicate that RDCN manages speeds
  153. above 700 Kb/sec. (if NUKE packspeed was compared to RDCN 140 Kb/sec). If
  154. we compare to BLZW, RDCN unpacks 560 Kb/sec. Packing compared to BLZW is
  155. 165 Kb/sec.
  156.  
  157. Well, as I said, I don't have access to xBench, but several other tests shows
  158. that RDCN unpacks more than 600 Kb/sec and generally packs more than 150
  159. Kb/sec.
  160.  
  161. CREDITS
  162. ~~~~~~~
  163. Ed Ross of Application Software for the actual algorithm. Simple, clear and
  164. fast! Thanks Ed!
  165.  
  166.  
  167. CONTACT
  168. ~~~~~~~
  169. Suggestions to "Niklas Sjoberg" 2:203/415.3@Fidonet
  170.  
  171.  
  172.